package datastrucure.tree;

import java.util.LinkedList;

/**
 * @Author Fizz Pu
 * @Date 2021/4/13 下午2:51
 * @Version 1.0
 * 失之毫厘，缪之千里！
 */

// 层序遍历
public class TraverseFolor {
    static class Node{
        private Node left;
        private Node right;
        private  int val;

        public Node(Node left, Node right, int val) {
            this.left = left;
            this.right = right;
            this.val = val;
        }
    }

    public static void traverse(Node node){
        if(node == null){
            return;
        }
        LinkedList<Node> queue = new LinkedList<>();
        queue.addLast(node);

        while (!queue.isEmpty()){
            int size = queue.size();
            int i = 0;
            System.out.print("第" + i + "层:");
            // 每一层
            // for(i = 0; i < queue.size(); i++) error是错误的
            for(i = 0; i < size; i++){
                Node tmp = queue.removeFirst();
                System.out.print(tmp.val + " ");

                if(tmp.left != null){
                    queue.addLast(tmp.left);
                }

                if(tmp.right != null){
                    queue.addLast(tmp.right);
                }
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Node node1 = new Node(null, null, 1);
        Node node2 = new Node(null, null, 2);
        Node node3 = new Node(null, null, 3);
        Node node4 = new Node(null, null, 4);
        Node node5 = new Node(null, null, 5);
        Node node6 = new Node(null, null, 6);
        Node node7 = new Node(null, null, 7);
        Node node8 = new Node(null, null, 8);
        node1.left = node2;
        node1.right = node3;
        node2.left = node4;
        node2.right = node5;
        node3.left = node6;
        node3.right = node7;
        node6.left = node8;
        traverse(node1);
    }

}
